import java.util.*;

public class Solution {
    //1.剑指 Offer 53 - II. 0～n-1中缺失的数字(与自然数比较)
    public int missingNumber(int[] nums) {
        int len = nums.length;
        for(int i = 0; i < len; i++){
            if(nums[i] != i){
                return i;
            }
        }
        return len;
    }
    //2.剑指 Offer 42. 连续子数组的最大和
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0];
        int sum = nums[0];
        for(int i = 1; i < len; i++){
            sum += nums[i];
            if(sum < nums[i]){
                sum = nums[i];
            }
            if(sum > max){
                max = sum;
            }
        }
        return max;
    }
    //3.下一个更大元素 I(暴力)
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //思路：遍历nums1，每拿到一个数字，假设为a，就从nums2中从后像前找比他大的数字
        //只要在碰到a之前拿到比他大的数字，说明就找到了，否则就是-1

        int[] ret = new int[nums1.length];
        int retIndex = 0;//ret数组的下标
        for(int i = 0; i < nums1.length; i++){
            int cur = nums2.length - 1;// 在nums2中从后向前找的指针
            //在nums2中从后向前找比他大的数字,若找到了,index就是当前下标
            int index = -1;
            while(nums1[i] != nums2[cur]){
                if(nums2[cur] > nums1[i]){
                    index = cur;
                }
                cur--;
            }
            if(index != -1){//找到了
                ret[retIndex++] = nums2[index];
            }else{
                ret[retIndex++] = -1;
            }
        }
        return ret;
    }
    //3.下一个更大元素 I(单调栈)
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //思路:单调栈法，遍历nums2，将元素依次入栈
        //若为空，就直接入栈
        //若不为空，就将入栈元素与栈顶元素比较，若比栈顶元素大，说明这就找到了一对下一个更大的元素
        //将这对元素放入HashMap中，最后遍历nums1对比HashMap的key值，将成立的键值对放入数组中

        int[] ret = new int[nums1.length];
        int retIndex = 0;//返回数组的下标
        Map<Integer, Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();//单调栈
        stack.push(nums2[0]);
        for(int i = 1; i < nums2.length; i++){
            //与栈顶元素比较，若大于栈顶元素，说明这是一对符合下一个是更大元素的键值对
            while(!stack.isEmpty() && nums2[i] > stack.peek()){
                map.put(stack.pop(), nums2[i]);
            }
            //两种可能的情况，一是不大于栈顶元素，入栈即可；二是大于栈顶元素，经过上个操作后，入栈即可
            stack.push(nums2[i]);
        }
        //栈中的剩余元素便是不符合的，所以放入map中，对应value为-1
        while(!stack.isEmpty()){
            map.put(stack.pop(), -1);
        }
        //遍历nums1，找对应键值对
        for(int i = 0; i < nums1.length; i++) {
            if (map.containsKey(nums1[i])) {
                ret[retIndex++] = map.get(nums1[i]);
            }
        }
        return ret;
    }
    //4.剑指 Offer 29. 顺时针打印矩阵(模拟边界法)
    public int[] spiralOrder(int[][] matrix) {
        //防止空数组
        if(matrix.length == 0){
            return new int[0];
        }
        int len = matrix[0].length;//长
        int high = matrix.length;//高
        int[] ret = new int[len * high];
        int retIndex = 0;//ret数组下标
        //模拟定界
        int top = 0;//上
        int down = high - 1;//下
        int left = 0;//左
        int right = len - 1;//右
        while(top <= down && left <= right){
            //存入上侧
            for(int i = left; i <= right; i++){
                ret[retIndex++] = matrix[top][i];
            }
            if(retIndex >= len * high){
                break;
            }
            //存入右侧
            for(int i = top + 1; i <= down; i++){
                ret[retIndex++] = matrix[i][right];
            }
            //存入下侧
            for(int i = right - 1; i >= left; i--){
                ret[retIndex++] = matrix[down][i];
            }
            if(retIndex >= len * high){
                break;
            }
            //存入左侧
            for(int i = down -1; i > top; i--){
                ret[retIndex++] = matrix[i][left];
            }
            top++;
            down--;
            left++;
            right--;
        }
        return ret;
    }
    //5.丢失的数字(模拟哈希表)
    public int missingNumber(int[] nums) {
        //模拟哈希表
        int len = nums.length;
        int[] hash = new int[len + 1];//缺少了一个，所以+1用来补全所有可能性
        //给表赋值
        for(int i = 0; i < len + 1; i++){
            hash[i] = i;
        }
        //把出现过的值赋值成-1;
        for(int i = 0; i < len; i++){
            hash[nums[i]] = -1;
        }
        //找出不是-1的
        for(int i = 0; i < len + 1; i++){
            if(hash[i] != -1){
                return hash[i];
            }
        }
        return -1;
    }
    //6.分发饼干(暴力)
    public int findContentChildren(int[] g, int[] s) {
        int count = 0;
        //给饼干大小排序,使得饼干能从小到大合理利用
        Arrays.sort(s);
        for(int i = 0; i < g.length; i++){
            for(int j = 0; j < s.length; j++){
                //找到合适的小饼干
                if(g[i] <= s[j]){
                    s[j] = -1;//吃过的饼干不能再吃
                    count++;
                    break;
                }
            }
        }
        return count;
    }
    //6.分发饼干(贪心)
    public int findContentChildren(int[] g, int[] s) {
        //贪心
        Arrays.sort(g);
        Arrays.sort(s);
        int curG = 0;
        int curS = 0;
        int count = 0;//计数器
        while(curG < g.length && curS < s.length){
            if(g[curG] <= s[curS]){//满足需求
                count++;
                curG++;
                curS++;
            }else{//向后找合适的饼干(能这么写是因为之前排过序)
                curS++;
            }
        }
        return count;
    }
    //7.一维数组的动态和(妙)
    public int[] runningSum(int[] nums) {
        int len = nums.length;
        int[] ret = new int[len];
        ret[0] = nums[0];
        for(int i = 1; i < len; i++){
            //每次加和时，加上上一个下标所指向的数组元素(之前元素的和),就可以优化时间
            ret[i] = ret[i - 1] + nums[i];
        }
        return ret;
    }
    //7.一维数组的动态和(进一步空间优化)
    public int[] runningSum(int[] nums) {
        int len = nums.length;
        for(int i = 1; i < len; i++){
            //每次加上一个数就OK
            nums[i] += nums[i - 1];
        }
        return nums;
    }
    //8.区域和检索 - 数组不可变
    public int[] array;
    public NumArray(int[] nums) {
        array = Arrays.copyOf(nums, nums.length);
    }

    public int sumRange(int left, int right) {
        int sum = 0;
        for(int i = left; i <= right; i++){
            sum += array[i];
        }
        return sum;
    }
    //9.找到所有数组中消失的数字(不使用额外空间,时间O(n))
    public List<Integer> findDisappearedNumbers(int[] nums) {
        //因为所有数的下标加一就是1~n之间的数
        //遍历，得到元素后将该元素可以表示的下标元素修改为负数
        //剩下最后不是负数的元素的下标+1即为所求
        for(int i = 0; i < nums.length; i++){
            //会修改元素为负数(不能直接乘-1，因为有相同元素)，所以用绝对值
            nums[Math.abs(nums[i]) - 1] = -Math.abs(nums[Math.abs(nums[i]) - 1]);
        }
        //找到不为负数的下标
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0){
                list.add(i + 1);
            }
        }
        return list;
    }
    //10.种花问题(暴力)
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        if(flowerbed.length == 1 && flowerbed[0] == 0){
            return true;
        }
        int count = 0;
        for(int i = 0; i < flowerbed.length; i++){
            if((flowerbed[i] == 0 && i + 1 < flowerbed.length && flowerbed[i + 1] == 0 && i - 1 < 0) ||
                    (flowerbed[i] == 0 && i + 1 < flowerbed.length && flowerbed[i + 1] == 0 && i - 1 >= 0 && flowerbed[i - 1] == 0)
                    || (flowerbed[i] == 0 && i - 1 >= 0 && flowerbed[i - 1] == 0 && i + 1 == flowerbed.length)){
                count++;
                flowerbed[i] = 1;
            }
        }
        if(count >= n){
            return true;
        }else{
            return false;
        }
    }
}
